package com.learning.datastruct.tree;

import com.learning.datastruct.common.Visitor;
import com.learning.datastruct.helper.printer.BinaryTreeInfo;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author ADMIN
 * @Classname BinaryTree
 * @date 2022/1/24 5:00
 */
@SuppressWarnings({"unchecked", "unused"})
public abstract class BinaryTree<E> implements BinaryTreeInfo {
    protected int size = 0;
    protected Node<E> root;

    protected static class Node<E> {
        protected E element;
        protected Node<E> left;
        protected Node<E> right;
        protected Node<E> parent;

        protected Node(E element, Node<E> parent) {
            this.element = element;
            this.parent = parent;
        }

        protected boolean hasTowChildren() {
            return this.left != null && this.right != null;
        }

        protected boolean isLeftChild() {
            return parent != null && parent.left == this;
        }

        protected boolean isRightChild() {
            return parent != null && parent.right == this;
        }
    }

    public void clear() {
        root = null;
        size = 0;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void preorderTraversal1(Visitor<E> visitor) {
        preorderTraversal1(root, visitor);
    }

    private void preorderTraversal1(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) {
            return;
        }
        visitor.stop = visitor.visit(node.element);
        preorderTraversal1(node.left, visitor);
        preorderTraversal1(node.right, visitor);
    }

    private void inorderTraversal1(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) {
            return;
        }
        inorderTraversal1(node.left, visitor);
        if (visitor.stop) {
            return;
        }
        visitor.stop = visitor.visit(node.element);
        inorderTraversal1(node.right, visitor);
    }

    private void postorderTraversal1(Node<E> node, Visitor<E> visitor) {
        if (node == null || visitor.stop) {
            return;
        }
        postorderTraversal1(node.left, visitor);
        postorderTraversal1(node.right, visitor);
        visitor.stop = visitor.visit(node.element);
    }

    /**
     * 层序遍历
     */
    public void levelOrderTraversal(Visitor<E> visitor) {
        if (root == null) {
            return;
        }
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            if (visitor.visit(node.element)) {
                return;
            }
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

    /**
     * 返回树的高度
     *
     * @return 树的高度
     */
    public int height1() {
        return height1(root);
    }

    private int height1(Node<E> node) {
        if (node == null) {
            return 0;
        }
        return Math.max(height1(node.left), height1(node.right));
    }

    public int height2() {
        if (root == null) {
            return 0;
        }
        int height = 0;
        // 当前层的元素数量
        int levelSize = 1;
        Queue<Node<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node<E> node = queue.poll();
            levelSize--;
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            // 如果当前层已经访问完毕 高度应该+1 且当前队列的size就是下一层元素的数量
            if (levelSize == 0) {
                height++;
                levelSize = queue.size();
            }
        }
        return height;
    }

    /**
     * 前驱节点
     *
     * @param node 节点
     * @return 前驱节点
     */
    protected Node<E> precessNode(Node<E> node) {
        if (node == null) {
            return null;
        }
        Node<E> p = node.left;
        if (p != null) {
            while (p.right != null) {
                p = p.right;
            }
            return p;
        }
        while (node.parent != null && node == node.parent.left) {
            node = node.parent;
        }
        return node.parent;
    }

    /**
     * 后继节点
     *
     * @param node 节点
     * @return 后继节点
     */
    protected Node<E> successor(Node<E> node) {
        if (node == null) {
            return null;
        }
        Node<E> p = node.right;
        if (p != null) {
            while (p.left != null) {
                p = p.left;
            }
            return p;
        }
        while (node.parent != null && node == node.parent.right) {
            node = node.parent;
        }
        return node.parent;
    }

    @Override
    public Object root() {
        return root;
    }

    @Override
    public Object left(Object node) {
        return ((Node<E>) node).left;
    }

    @Override
    public Object right(Object node) {
        return ((Node<E>) node).right;
    }

    @Override
    public Object string(Object node) {
        return ((Node<E>) node).element;
    }
}
